package 极客算法训练营.chapter08;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class 子集 {
    class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            Deque<Integer> path = new LinkedList<>();
            dfs(0, nums, path, ans);
            return ans;
        }

        public void dfs(int depth, int[] nums, Deque<Integer> path, List<List<Integer>> ans) {
            if (depth == nums.length) {
                ans.add(new ArrayList<>(path));
                return;
            }
            //不包含当前元素
            dfs(depth + 1, nums, path, ans);
            //包含当前元素
            path.addLast(nums[depth]);
            dfs(depth + 1, nums, path, ans);
            path.removeLast();
        }
    }
}
